package com.递归2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 *
 * 示例:
 *
 * 输入: 5
 * 输出:
 * [
 *      [1],
 *     [1,1],
 *    [1,2,1],
 *   [1,3,3,1],
 *  [1,4,6,4,1]
 * ]
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/recursion/4mb3s/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 杨辉三角 {
  public static class Solution {
        int[][] storage = null;
        public static Map<Integer,List<List<Integer>>> cache = new HashMap<>();
       /**
        * 解题思路
        * 递推关系：f(x,y) = f(x-1,j-1)+f(x-1,j)
        * 记忆：storage[x][y]
        * 终止条件：每一行的第一个和最后一个为1
        * @param numRows
        * @return
        */
        public static List<List<Integer>> generate(int numRows) {
           List<List<Integer>> list = new ArrayList<>();
            for (int row = 0; row < numRows; row++) {
                List<Integer> rowList = new ArrayList<>();
                for (int index = 1; index <= row + 1; index++) {
                    int number = genNum(row+1,index);
                    rowList.add(number);
                }
                list.add(rowList);
            }
            return list;
        }

       public static int genNum(int row, int index) {
            if(index==1 || index == row){
                return 1;
            }

           return genNum(row-1,index-1)+genNum(row-1,index);
       }


       public static void main(String[] args) {
           List<List<Integer>> generate = generate(3);
       }
    }
}




